perm filename FUZZY.MAN[RUT,LSP] blob
sn#345125 filedate 1978-03-22 generic text, type T, neo UTF8
FUZZY REFERENCE MANUAL
Rick LeFaivre
Computer Science Department
Rutgers University
March 22, 1977
CONTENTS
←←←←←←←←
1. INTRODUCTION . . . . . . . . . . . . . . . . 2
2. A BRIEF INTRODUCTION TO FUZZY . . . . . . . 3
2.1 Fuzzy Expressions . . . . . . . . . . . 3
2.2 The Associative Net . . . . . . . . . . 4
2.3 Pattern-Matching . . . . . . . . . . . . 5
2.4 Contexts and Backtrack States . . . . . 7
2.5 Procedures . . . . . . . . . . . . . . . 9
2.6 Deductive Mechanisms . . . . . . . . . . 12
3. FUZZY REFERENCE GUIDE . . . . . . . . . . . 16
3.1 Introduction . . . . . . . . . . . . . . 16
3.2 Language Primitives . . . . . . . . . . 16
3.3 Pattern Functions . . . . . . . . . . . 25
3.4 Variables of Interest . . . . . . . . . 27
3.5 Debugging Aids . . . . . . . . . . . . . 29
4. REFERENCES . . . . . . . . . . . . . . . . . 31
5. INDEX . . . . . . . . . . . . . . . . . . . 32
FUZZY REFERENCE MANUAL Page 2
1. INTRODUCTION
←←←←←←←←←←←←←←←
The FUZZY programming language has been in use as a research
tool at several sites around the world since August of 1974. A
preliminary description of the language was presented in [1], and
a version programmed in UNIVAC 1110 LISP was described in [2].
This manual serves as a description of the current implementation
of FUZZY, which is programmed in RUTGERS/UCI LISP for the PDP-10.
A number of additions have been made in this latest version,
including a data context mechanism, backtrackable property list
functions, the ability to compute "net differences", and a more
powerful debugging package.
FUZZY may be classified as a "second generation" AI
language, along with such systems as MICRO-PLANNER, CONNIVER, and
QLISP (see [6] for a general overview of these languages). Its
spiritual predecessor was FUZZY-PLANNER, a system which was
conceived by Rob Kling and the author in 1972 and was
subsequently developed on paper by Kling [7], but which was never
implemented. FUZZY is an attempt to synthesize many of the "good
ideas" of previous AI languages while providing facilities for
the efficient storage, retrieval, and manipulation of knowledge
which is vague and uncertain in nature. The language was
constructed in such a way that it could be directly embedded in
LISP (unlike previous systems), and is therefore much more
efficient than languages such as MICRO-PLANNER which require a
run-time monitor. LISP and FUZZY primitives may be freely
intermixed, and FUZZY functions may be called from compiled LISP
code if desired.
This manual is divided into two major sections, the first
consisting of a brief introduction to major aspects of the
language, and the second containing detailed descriptions of the
various system primitives. Note that this manual is intended as
a reference manual, and as such contains few (if any) realistic
←←←←←←←←←
examples. For discussions of how FUZZY can be utilized to
represent a variety of different forms of fuzzy information,
consult references [1] through [5].
FUZZY REFERENCE MANUAL Page 3
2. A BRIEF INTRODUCTION TO FUZZY
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
2.1 Fuzzy Expressions
←←←←←←←←←←←←←←←←←←←←←
FUZZY is in essence a many-valued programming language. By
this we mean that, unlike traditional languages in which
expressions evaluate to a single value, FUZZY expressions may
return both a value and a "fuzzy truth-value", or Z-value*.
←←←←← ←←←←←←←
Z-values are numeric, and fall in a range specified by the LISP
variables ZLOW and ZHIGH. This range is initially defined as
[0,1], but it may be changed if desired via the RANGE function.
For example,
(RANGE -1 +1)
changes the range to [-1,+1]. Although FUZZY makes no
assumptions about the interpretation given a particular Z-value,
it is traditional to associate ZLOW with "false" and ZHIGH with
"true".
Internally, Z-values are stored by CONSing the Z-value to
the value it modifies. This usage of a standard LISP construct
for the representation of fuzzy information allows non-FUZZY
(i.e., LISP) programs to create and modify fuzzy data in a
unified manner. Primitives are available for retrieving the
value (VAL) or Z-value (ZVAL) portions of an expression, and for
computing logical combinations of fuzzy expressions (ZAND, ZOR,
ZNOT). In all cases, a default Z-value of ZHIGH is provided by
the system if no Z-value is present explicitly.
In addition to being able to return values and Z-values,
FUZZY expressions may either succeed or fail in a manner similar
←←←←←←← ←←←←
to other AI languages (see [6]). Failure is indicated by simply
returning a value of FAIL (which, like NIL in LISP, is bound to
itself), with any other value constituting success. Several
variations of a standard IF-THEN-ELSE mechanism are available for
controlling success and failure of individual expressions. It
should be noted that there is a definite distinction made between
expressions which return a low Z-value and those which fail. The
statement that the moon contains no cheese, which we might
represent as:
[(CONTAINS MOON CHEESE) . 0]
is quite different from the statement that we have failed to find
any information pertaining to the presence of cheese in the moon.
----------------
*The term "Z-value" was chosen so as not to give any semantic
connotations to the usage of this numeric modifier, since it can
represent a conventional truth-value, a fuzzy set grade of
membership, a degree of certainty or belief, a simple weight, or
anything else the user wishes.
FUZZY REFERENCE MANUAL Page 4
2.2 The Associative Net
←←←←←←←←←←←←←←←←←←←←←←←
In addition to standard LISP data structures, FUZZY allows
fuzzy knowledge to be explicitly represented by maintaining an
associative network of assertions similar to that of other AI
←←←←←←←←←←
languages. Any arbitrary LISP list structure may be entered into
this net -- no restrictions are placed on the complexity of
assertions. In addition, an assertion may have a Z-value
associated with it if desired (as usual, if no Z-value is present
an implicit value of ZHIGH is assumed).
Adding to the net. Assertions are added to the net using
←←←←←←←←←←←←←←←←←←
the ADD function, for example:
(ADD (ROSES ARE RED))
The argument passed to ADD is called a skeleton -- it may contain
←←←←←←←←
variables and expressions which will be replaced by their values
when the skeleton is instantiated by the system. We will examine
←←←←←←←←←←←←
the structure of skeletons and the instantiation process in more
detail in the next section. Note that the above skeleton does
not contain any variables or expressions; it thus instantiates
to itself, and we term it a "fully-instantiated" skeleton.
Z-values may be associated with assertions by including a
second argument to ADD. Thus,
(ADD (VIOLETS ARE BLUE) 0.8)
adds the construct [(VIOLETS ARE BLUE) . 0.8] to the net. The
Z-value argument is evaluated in the LISP sense, so that
←←←←←←←←←
arbitrary expressions which compute Z-values may be utilized.
Retrieving from the net. Assertions may be retrieved from
←←←←←←←←←←←←←←←←←←←←←←←←
the net using the FETCH primitive. The net is said to be
associative since only part of the assertion need be specified to
←←←←←←←←←←←
retrieve it -- neither its "location" nor its full structure need
be known. The first argument to FETCH is thus a pattern which
←←←←←←←
will be matched against the assertions in the net. For example,
the expression:
(FETCH (PRETTY ?))
will match any assertion of the form (PRETTY -), returning the
assertion as its value (the pattern-matcher will be discussed in
detail in the next section). If no assertion of the indicated
form is present, FETCH fails (i.e., returns FAIL). If more than
one assertion is found, the one with the highest Z-value is
returned. This convention can be overridden by passing FETCH a
second argument which is interpreted as an acceptable Z-value
range. The general form is:
(FETCH <pat> [<from>,<to>])
which means that only assertions with a Z-value in the specified
FUZZY REFERENCE MANUAL Page 5
range are to be examined, and the matching assertion with a
Z-value closest to <from> is to be returned. Thus a range of
[0,1] will cause the assertion with the smallest Z-value (closest
to 0) to be returned, and [1,0] the largest ([1,0] is the
standard default range, and is bound to the LISP variable
ZRANGE). If a single integer <n> is entered as the second
argument to a FETCH, a range of [ZHIGH,<n>] is assumed, i.e.,
return the matching assertion with the highest Z-value greater
than or equal to <n>.
Removing from the net. Assertions may be removed from the
←←←←←←←←←←←←←←←←←←←←←←
net via the REMOVE function, e.g.,
(REMOVE (SUGAR IS SWEET))
REMOVE takes a skeleton to be instantiated as its only argument.
The indicated assertion is removed regardless of what Z-value is
associated with it. If the indicated assertion is not found in
the net, REMOVE fails.
2.3 Pattern-Matching
←←←←←←←←←←←←←←←←←←←←
Instantiation and evaluation. FUZZY's pattern-matching
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
capabilities are similar to those of QLISP, although FUZZY offers
more built-in pattern functions. Like other AI languages, FUZZY
operates in "inverse quote mode", i.e., primitive symbols in
skeletons and patterns stand for themselves, and variables and
expressions are flagged as such. However in FUZZY this concept
is extended to include functional arguments as well as skeletons
and patterns. Each primitive function specifies whether its
arguments are to be evaluated in the normal LISP sense, or
←←←←←←←←←
instantiated, with flagged variables and expressions replaced by
←←←←←←←←←←←←
their values. The user may override the default interpretations
via use of the instantiation operator (!) or evaluation operator
(&). For example, the primitive ADD specifies that its first
argument be instantiated and its second argument be evaluated.
Thus
(ADD (BIG !OBJECT) (TIMES SIZE BIAS))
(where !OBJECT is a FUZZY variable) may be written instead of:
(ADD !(BIG !OBJECT) &(TIMES SIZE BIAS))
However, one may override the default interpretations:
(ADD &(CAR OBJECTS) !AVSIZE)
The "!" and "&" operators may also be used within skeletons
and patterns; for example, (A !X &Y) instantiates to (A B C) if
the FUZZY variable !X is bound to B and the LISP variable Y is
bound to C. "Segment" instantiation (!!) and evaluation (&&)
operators are also available for use within skeletons and
patterns; for example, if !X has FUZZY value (B C) and Y has
FUZZY REFERENCE MANUAL Page 6
LISP value (D E), (A !!X &&Y) instantiates to (A B C D E)
[whereas (A !X &Y) would instantiate to (A (B C) (D E))].
Variables, skeletons, and patterns. It might be useful to
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
pause at this point and examine some of the terminology being
used in this section. Variables may be bound in both FUZZY and
←←←←←←←←←
LISP. A FUZZY variable is assigned a value via pattern-matching,
as described below. Its value is retrieved via the process of
instantiation, using one of the operators "!" or "!!". The
segment instantiation operator "!!" may be used only within
skeletons and patterns, whereas the "!" operator may be used to
instantiate a FUZZY variable or skeleton in any situation (e.g.,
as an argument to a LISP function). A LISP variable is assigned
a value using one of the LISP binding mechanisms (e.g., SETQ).
It (and, indeed, any LISP expression) may be referenced within
skeletons and patterns via use of the "&" and "&&" operators,
which simply pass control to the LISP evaluator. For the sake of
completeness, "&" may also precede expressions to be evaluated in
other situations (e.g., as arguments to functions), although such
usage is redundant. As a final example, if the FUZZY variable
!VAR has been assigned the value (A B) and the LISP variable VAR
is bound to (C D), then the skeleton:
(VAR !VAR !!VAR &VAR &&VAR)
instantiates to:
(VAR (A B) A B (C D) C D)
The term skeleton refers to list structures which contain only
←←←←←←←←
constants (i.e., symbols with no prefix) or the prefix operators
"!", "!!", "&", or "&&". After instantiation, skeletons contain
only constant symbols. Patterns may also contain a variety of
←←←←←←←←
pattern functions which control the pattern-matching process, as
described below.
Pattern-matching. FUZZY variables may be assigned values
←←←←←←←←←←←←←←←←←
via the "?" (item) and "??" (segment) operators. For example,
using the primitive MATCH:
(MATCH (?X ??Y) ((A B) C D E))
binds !X to (A B) and !Y to (C D E). "?" and "??" may also stand
alone to match an arbitrary item or segment with no variable
assignments. Note that in addition to MATCH, which matches an
arbitrary pattern against a skeleton, there is a more
conventional (and efficient) BIND primitive which binds a single
variable to the value of an expression. Thus:
(BIND ?X (CAR L))
has the same effect as:
(MATCH ?X &(CAR L))
FUZZY REFERENCE MANUAL Page 7
although the former is more efficient.
FUZZY also provides a wide range of pattern functions which
allow complex conditional patterns to be constructed. For
example, the pattern:
(*OR 6 SIX VI)
matches either the number 6 or one of the atomic symbols SIX or
VI.
(*AND (*OR 6 SIX VI) ?NUM)
also binds the item matched (6, SIX, or VI) to the FUZZY variable
!NUM. This pattern may be abbreviated by writing:
(*ANY ?NUM (6 SIX VI))
As other examples,
(FETCH (*CON ?NEWS CHINA))
retrieves the assertion with the highest Z-value which contains
(at any level) the atom CHINA, binding the entire assertion to
the FUZZY variable ?NEWS; and
(FETCH (*R (BIG ?OB) (FETCH (RED !OB))) 0.9)
searches for an object which is quite (0.9) big, but which is
restricted (*R) to being red.
2.4 Contexts and Backtrack States
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
It is often convenient to maintain several different
associative data bases (perhaps dealing with different subjects,
different time periods, etc.), with the ability to access each
data base independently. FUZZY provides such a feature through
the context mechanism. A new context is activated by invoking
←←←←←←←
the CONTEXT function, which takes as its argument an atomic
symbol which is to be the "name" of the new active context (NIL
is used to indicate the initial context), and returns the name of
the previously active context. All net modifications and
accesses will only refer to the current context, ignoring all
other (inactive) contexts. The user may switch back and forth
between several contexts at will, perhaps keeping the context
names in a tree structure to provide a hierarchical structure.
It is also often helpful to have a mechanism whereby
modifications can be made to a data base on a "trial" basis
(perhaps during a hypothetical search) and then be undone if they
prove to be undesirable. This is accomplished in FUZZY via the
saving of states, or snapshots of the system at a particular
←←←←←←
time. The function SAVE (of no arguments) returns such a state,
which acts as a backtrack point which can later be passed to the
FUZZY REFERENCE MANUAL Page 8
RESTORE primitive to cause all modifications made since the state
was saved to be undone. All net modifications, FUZZY variable
bindings, and LISP variables and property lists modified via
BIND, ZPUT, ZREMPROP, etc. are subject to backtracking. For
example,
(SETQ STATE (SAVE))
.
.
.
(RESTORE STATE)
restores things to their previous state. It is also possible to
use the NETDIF primitive to compute a "difference" between the
current net and the net at some previous state. This capability
allows for the computation of a sequence of incremental state
differences before a state is restored to. Note that once a
state is restored to, all states saved since the original state
are defunct, that is, once a backtrack point is passed during
backtracking it disappears.
It is occasionally desirable to make certain changes
permanent, so that they cannot be undone by a subsequent RESTORE.
Such a capability is provided by the primitive FINALIZE, which
takes a previously saved state as an argument and finalizes all
net modifications, etc., made since the state was created.
Again, all states saved since the original state was created are
defunct.
Although the user may construct his own backtrack control
regime using these primitives, a number of backtrack mechanisms
are already provided by the system. For example,
(DO? <exp1> <exp2> . . .)
evaluates each expression and returns the value of the last one,
just like the standard LISP DO (PROGN), except that it backtracks
and undoes any changes made. It is equivalent to:
((LAMBDA (S V) (RESTORE S) V) (SAVE) (DO <e1> <e2> . . .))
DO! is similar to DO?, except that it FINALIZEs everything done
so that it will not be undone. Similarly,
(BIND! ?X <expr>)
may be used to bind a FUZZY variable such that the binding will
not be undone upon subsequent backtracking. It is identical to:
(DO! (BIND ?X <expr>)
Finally, the FOR statement provides a powerful recursive
backtrack capability. It may be used to iterate through an
explicit list of alternatives or to iterate through all
assertions in the net which match a given pattern (other
FUZZY REFERENCE MANUAL Page 9
variations of FOR will be discussed in section 2.6). As an
example of the use of FOR, each of the following expressions will
list all blocks which are either very pretty, very red, or very
big:
(FOR FETCH: (BLOCK ?X)
(IFANY (FETCH (PRETTY !X) 0.9)
(FETCH (RED !X) 0.9)
(FETCH (BIG !X) 0.9)
THEN: (PRINT !X)))
(FOR FETCH: (BLOCK ?X)
(FOR ?REL (PRETTY RED BIG)
(FETCH (!REL !X) 0.9)
(PRINT !X)))
(FOR ?REL (PRETTY RED BIG)
(FOR FETCH: (!REL ?X) ZVAL: 0.9
(FETCH (BLOCK !X))
(PRINT !X)))
Upon entry to the FOR statement a SAVE is automatically
performed. For each successful match (either explicit, or
implicit via the FETCH statement) the expressions within the FOR
are evaluated. If any of the expressions fail, or if (BACK) is
evaluated, a RESTORE is performed and the next alternative is
tried (if no alternatives remain, the FOR fails). The next
alternative may also be tried without backtracking via (NEXT), or
the loop may be exited via (EXIT). A default (BACK) is placed at
the end of the loop, so that:
(FOR FETCH: (RED ?X) (REMOVE (RED !X)) (NEXT))
or
(FOR FETCH: (RED ?X) (DO! (REMOVE (RED !X))))
is necessary to remove all the red objects from the net, since:
(FOR FETCH: (RED ?X) (REMOVE (RED !X)))
would have no effect because of the backtracking. Note that
FOR FETCH: automatically orders the alternative assertions in
increasing or decreasing order by Z-value, under the control of
the optional ZVAL: field (which is identical to the range
argument in FETCH).
2.5 Procedures
←←←←←←←←←←←←←←
A FUZZY procedure is much like a MICRO-PLANNER theorem or
QLISP QLAMBDA function: it takes a skeletal argument which is
matched against a procedure pattern, the procedure is entered if
←←←←←←←←← ←←←←←←←
the match is successful, and a result is computed. For example,
the following simple procedure transforms a completely
parenthesized infix expression to a prefix expression, i.e.,
(PREFIX (A * (B + C))) returns (* A (+ B C)):
FUZZY REFERENCE MANUAL Page 10
(PROC NAME: PREFIX (*OR (?L ?OP ?R) ?ATOM)
(IF (BOUND !ATOM) THEN: (SUCCEED !ATOM)
ELSE: (SUCCEED (!OP &(PREFIX !L) &(PREFIX !R)))))
The NAME: field is optional -- if absent a unique name will be
generated by the system (this name is returned as the value of
the PROC statement). Procedures may either succeed (returning
←←←←←←←
both a value and a Z-value) or fail, just like standard system
←←←←
primitives. Success is caused by (SUCCEED <skel> <zval>) or
simply (SUCCEED), which returns the instantiated procedure
pattern (a default (SUCCEED) is placed at the end of each
procedure in case evaluation "falls off the end"). Failure may
be caused by simply (SUCCEED FAIL). However, in this case we
typically want to restore the system to its state before the
procedure was entered. This state is automatically saved, and
may be restored to at any time via (RESTORE). We thus normally
do (FAIL), which is equivalent to (RESTORE) followed by
(SUCCEED FAIL). It is also occasionally desirable to finalize
everything done by a procedure before succeeding. This may be
accomplished by preceding the SUCCEED statement with (FINALIZE),
or simply executing (SUCCEED! . . .). A standard GOTO statement
is also available for transferring control within a procedure.
Global variables. It should be noted that FUZZY operates in
←←←←←←←←←←←←←←←←←
a kind of "inverse declaration mode": all FUZZY variables are
assumed to be local to the procedure in which they appear unless
they are declared to be global. This declaration may be made
explicitly in the PROC statement, e.g.:
(PROC GLOBAL: (!GL1 !GL2) . . .)
or implicitly (for all procedures) via the GLOBAL function:
(GLOBAL !GL1 !GL2 . . .)
Since in the vast majority of cases variables are used only
locally, this feature relieves the user of much of the burden of
making variable declarations.
Global control. The major difference between FUZZY
←←←←←←←←←←←←←←←
procedures and units of procedural knowledge in other programming
languages is in the amount of global control a procedure
←←←←←← ←←←←←←←
exercises over its local computations. For example, most
conventional programming languages (FORTRAN, LISP) exercise no
global control -- all decisions (e.g., when to exit from a
function) are made at the local level by statements within the
procedure. On the other hand, MICRO-PLANNER monitors the
execution of its procedures (theorems), looking for statements
which fail (return NIL) and taking some global action
(backtracking) when necessary. We are faced with the question of
what form of global control (if any) should be built into a FUZZY
procedure. Consider a typical example: we want a procedure to
succeed only if each of its local expressions succeeds with a
Z-value above some threshold value. Now, this could of course be
done using only local control -- by inserting tests of the
FUZZY REFERENCE MANUAL Page 11
Z-value of each expression into the procedure -- but this would
clutter up the routine with rather uninteresting and repetitive
local computations, obscuring its overall structure. In
addition, each procedure requiring this particular global control
regime would have to have the necessary local computations built
in -- a clearly inelegant solution. We would like to be able to
simply specify the Z-value threshold and have the system perform
the necessary manipulations:
(PROC ZVAL: <n> <pattern> <e1> <e2> . . .)
A fixed procedure mechanism of this form would be the FUZZY
equivalent of the simple control present in MICRO-PLANNER
theorems. However, as mentioned earlier, there may be other
forms of global control which might be desirable -- for example:
ignore all failures; succeed only if at least <n> of the
statements succeed; succeed only if some function of the
←←←←←←←←
individual Z-values exceeds a threshold (e.g., a threshold
operator); return as a Z-value the minimum (maximum, sum,
product) of the individual Z-values encountered; etc. FUZZY
procedures allow all of these forms of global control (and more)
via the specification of procedure demons.
←←←←←←←←← ←←←←←←
Procedure demons. A procedure demon is a LISP function
←←←←←←←←←←←←←←←←←
which is associated with a procedure, and which is given control
after each expression of the procedure is evaluated (including
expressions within FOR statements). The demon is passed the
result of the evaluation, the Z-value associated with the
procedure, and an "accumulated Z-value" which may be dynamically
computed by the demon. When the procedure is exited the demon is
called one last time with a value of DONE in order to make any
necessary final computations (e.g., computing an average). For
example, consider the case of succeeding only if all of the
expressions in a procedure succeed with a Z-value above some
threshold, keeping track of the minimum Z-value encountered. A
procedure demon which exercises this form of global control can
be defined as follows (this is in fact FUZZY's standard default
demon):
(DE *DEMON (V ZV AC)
(COND [(EQ V FAIL) (FAIL)]
[(EQ V DONE) AC]
[(*LESS (ZVAL V) ZV) (FAIL)]
[T (*MIN (ZVAL V) AC)]))
The value returned by a procedure demon is saved by the
system and becomes the new accumulated Z-value upon the next call
to the demon. Thus in addition to checking for statements which
fail or fall below the threshold (and causing the procedure to
fail if one is found), *DEMON keeps track of the lowest Z-value
encountered, as desired. The final accumulated Z-value (i.e.,
the value returned by the demon after it is passed DONE) is
typically returned as the Z-value portion of the procedure
result. A procedure which uses *DEMON might be defined as
follows:
FUZZY REFERENCE MANUAL Page 12
(PROC DEMON: *DEMON ZVAL: 0.5 ACCUM: 1.0 . . .)
This indicates that the demon for this procedure is *DEMON, the
threshold Z-value is 0.5, and the initial accumulated Z-value is
1.0 (i.e., this is the value used the first time the demon is
called after entering the procedure). The DEMON:, ZVAL:, and
ACCUM: fields are all optional, with default values of *DEMON,
ZLOW, and ZHIGH, respectivey, assumed.
If a procedure demon of NIL is specified, no demon calls are
made (i.e., the procedure is evaluated in a manner similar to a
LISP PROG, with only local control available). Other procedure
demons may be written by the user to specify unique forms of
global control (see [2]). The motivation behind the procedure
demon mechanism is that once a library of frequently-used
procedure demons is built up, the user may easily specify a
variety of global control regimes. He is thus relieved of much
of the "dirty work" of directly manipulating Z-values in the
programs he writes. Indeed, in many cases the user need not even
be aware that he is working with fuzzy information.
2.6 Deductive Mechanisms
←←←←←←←←←←←←←←←←←←←←←←←←
One of the major features of AI languages is the availablity
of deductive mechanisms which utilize procedures to "deduce"
assertions which are not present explicitly in the data base.
FUZZY provides a variety of methods of invoking procedures for
use in this manner.
Direct invocation. FUZZY procedures may be called directly
←←←←←←←←←←←←←←←←←←
by name in a manner similar to LISP functions. For example, the
following procedure may be used to deduce whether an object is
LITTLE, using the definition that any object which is not BIG is
LITTLE:
(PROC NAME: DEDUCE-LITTLE (LITTLE ?X)
(ZNOT (FETCH (BIG !X) [0,1])))
If we had earlier entered:
(ADD (BIG ELEPHANT) 0.9)
and we now request:
(DEDUCE-LITTLE (LITTLE ELEPHANT))
the assertion [(LITTLE ELEPHANT) . 0.1] is returned. The usage
of ZNOT, along with the standard procedure demon, causes the
desired Z-value to be computed (elephants are not very little).
If (BIG ELEPHANT) had not been found in the net, the call to
DEDUCE-LITTLE would have failed (again, because of the action of
the standard procedure demon).
FUZZY REFERENCE MANUAL Page 13
Note that in addition to using a skeletal
(fully-instantiated) argument like (LITTLE ELEPHANT), a procedure
may also be given a simple pattern as an argument. The pattern
←←←←←←←
may contain only the "?" and "?X" pattern functions, and each
such construct must be matched against either a
fully-instantiated item or another "?Y" pattern in the pattern of
the procedure being invoked. Such variables will be initially
unbound, and their usage with the operators "!" and "!!" is
treated as if "?" or "??" were present instead. For example,
(DEDUCE-LITTLE (LITTLE ?WHO))
will cause the ?X in the procedure DEDUCE-LITTLE to be unbound,
so that the !X in the pattern (BIG !X) is treated as if it were
?X. An object which is not big is thus retrieved from the net
and returned as being little -- the name will be bound to ?WHO in
the calling pattern. In fact, since the Z-value range in the
FETCH is [0,1], the least big (or "most little") object in the
net will be returned.
Invoking several procedures. Often there are several
←←←←←←←←←←←←←←←←←←←←←←←←←←←←
procedures which might be used to compute a result, and the user
is not sure which one will be successful. Such a situation may
be handled in FUZZY by using the TRY function. For example,
(TRY (P1 P2 P3) (LITTLE ELEPHANT))
will call each of the procedures P1, P2, and P3 with
(LITTLE ELEPHANT) as its argument until one succeeds. If none
succeeds, the TRY fails. TRY may also be given a Z-value range
like FETCH, e.g.,
(TRY (P1 P2 P3) (LITTLE ?WHO) 0.5)
will keep trying until a Z-value of at least 0.5 is returned.
Note that the list of functions to try is instantiated -- one
could make this list variable at run time via something like
(TRY !FUNCS . . .).
It is occasionally desirable to iterate through all
assertions which can be deduced utilizing a specified set of
procedures. This may be accomplished by using the FOR TRY:
version of the FOR statement. For example, the following lists
all objects which can be proven to be little via use of one of
the indicated procedures:
(FOR TRY: (P1 P2 P3) (LITTLE ?X) (PRINT !X))
Pattern-directed procedure invocation. Finally, we come to
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
one of the major contributions of AI languages: the ability to
automatically invoke appropriate procedures without having to be
aware of their names (or even their very existance). The
pattern-directed procedure invocation facilities of FUZZY are
similar to those of MICRO-PLANNER. In addition to ADD, REMOVE,
and FETCH, which operate only on the associative net, FUZZY
FUZZY REFERENCE MANUAL Page 14
supports ASSERT, ERASE, and DEDUCE primitives which cause
procedures to be invoked when assertions are added to or removed
from the net or are requested as goals to be deduced. Such
procedures are added to the data base via:
(ADD <type> <proc>)
where <type> is ASSERT:, ERASE:, or DEDUCE:, and <proc> is a
procedure name or a PROC statement. Assert and erase procedures
may be used for data base management in a manner similar to
antecedant and erasing theorems in MICRO-PLANNER. For example,
the following procedure assures that an object is in only one
place at a time, and that only one object can occupy a given
location:
(ADD ASSERT:
(PROC (AT ?OB ?LOC)
(IF (FETCH (AT (*NOT ? !OB) !LOC))
THEN: (FAIL)
ELSE: (IF (FETCH (AT !OB (*NOT ?L !LOC)))
THEN: (REMOVE (AT !OB !L))
ELSE: (SUCCEED))) ))
In addition to DEDUCE, which simply calls all deduce
procedures which match its argument in a manner similar to TRY,
FUZZY provides a GOAL primitive which first uses FETCH to see if
a matching assertion is present in the net. If not, it performs
a DEDUCE in an attempt to deduce the desired assertion. Both
DEDUCE and GOAL take an optional Z-value range (like that of
FETCH), and will continue until an assertion is found (or
computed) with a Z-value in the desired range. As an example of
a simple deduce procedure, the following says in effect that all
tricky people are dishonest:
(ADD DEDUCE:
(PROC (DISHONEST ?X)
(GOAL (TRICKY !X)) ))
If (DEDUCE (DISHONEST DICK)) is ever requested [or
(GOAL (DISHONEST DICK)), where the desired assertion is not
present in the net], the above procedure will be automatically
invoked. The original DEDUCE or GOAL expression will then
succeed if (TRICKY DICK) can be found in the net (or deduced
using some other deduce procedure), returning a Z-value equal to
that of (TRICKY DICK).
In addition to the FOR FETCH: and FOR TRY: primtives already
discussed, versions of the FOR statement are also available for
iterating through all assertions accessible via DEDUCE or GOAL.
For example, the following expression lists all dishonest people
who are present explicitly in the net, or who can be proven to be
dishonest through use of any available deduce procedures:
(FOR GOAL: (DISHONEST ?Y) (PRINT !Y))
FUZZY REFERENCE MANUAL Page 15
Note, however, that the deduce procedure shown above will only
return one dishonest (i.e., tricky) person. This is exactly the
←←←
case where we want our deduce procedure to act like a generator
←←←←←←←←←
in the CONNIVER sense. We would like it to iterate through all
←←←
of the dishonest people it knows about, which in this case are
all tricky people, returning them one at a time until the
original FOR exits from its loop. This may be accomplished in
FUZZY via the SUCCEED? primitive. SUCCEED? is identical to
SUCCEED, except that it saves the current program state of the
procedure so that it can be restarted by a higher-level FOR
(TRY:, DEDUCE:, or GOAL:) if necessary. Our example now becomes:
(ADD DEDUCE:
(PROC (DISHONEST ?X)
(FOR GOAL: (TRICKY !X)
(SUCCEED?)) ))
when called either directly or via a TRY, DEDUCE, or GOAL
statement, this procedure will return the first tricky person
found as being dishonest just as in the original version. When
invoked by a FOR statement, however, the procedure will act like
a generator, returning one tricky person at a time until it runs
out or the FOR is satisfied.
In summary, the wide variety of deductive mechanisms
available in FUZZY gives the user the choice of invoking
procedures directly when efficiency is critical, or utilizing the
pattern-directed invocation mechanism in an attempt to "diffuse"
procedural knowledge throughout the system.
FUZZY REFERENCE MANUAL Page 16
3. FUZZY REFERENCE GUIDE
←←←←←←←←←←←←←←←←←←←←←←←←
3.1 Introduction
←←←←←←←←←←←←←←←←
This section briefly describes each of the primitives
currently available in FUZZY. The complete calling sequence for
each primitive is given, with meta-linguistic variables enclosed
in <angle brackets>. Arguments which will be evaluated by the
system are indicated by preceding them with an ampersand
(&<...>), and arguments which will be instantiated by the system
are indicated by preceding them with an exclamation mark
(!<...>). All other arguments are normally neither evaluated nor
instantiated, with special cases described where appropriate.
Default values for missing arguments are specified where
necessary -- note that the default value for a missing &<zval>
argument is always ZHIGH, and the default value for a missing
!<zrange> argument is always &ZRANGE.
3.2 Language Primitives
←←←←←←←←←←←←←←←←←←←←←←←
(ACCUM: <proc> &<new accum>)
Changes the initial accumulated Z-value associated with
the indicated procedure. The value returned is the old
accumulated Z-value. If <new accum> is missing, the
current initial accumulated Z-value is returned without
change. <proc> will be evaluated if it is non-atomic.
(ADD !<skel> &<zval>) or (ADD <type> <proc>)
Adds (<skel> . <zval>) to the current associative net.
If the first argument is DEDUCE: (or D:), ASSERT: (or
A:), or ERASE: (or E:), the second argument should be a
procedure name or an expression which evaluates to a
procedure name (usually a PROC statement). Subject to
subsequent backtracking.
(ASSERT !<skel> &<zval>)
Adds (<skel> . <zval>) to the net and calls all assert
procedures which match <skel>. Fails if any of the
assert procedures fail (in which case <skel> is removed).
The assert procedures called may initially access <skel>
via (VAL) and <zval> via (ZVAL).
(BACK !<skel> &<zval>)
Causes the current FOR statement to backtrack and try the
next alternative. If no alternatives remain, a value of
(<skel> . <zval>) is returned as the value of the FOR
statement. Default <skel> is FAIL.
FUZZY REFERENCE MANUAL Page 17
(BIND <var> &<exp>)
Binds <var> (a LISP [X] or FUZZY [?X] variable) to the
value of <exp>. Subject to subsequent backtracking.
(BIND! <var> &<exp>)
Binds <var> to the value of <exp> such that the binding
will not be undone upon subsequent backtracking.
Conceptually identical to:
(DO! (BIND <var> <exp>))
If <var> is a LISP variable, BIND! is equivalent to SETQ.
(BOUND <var>)
Fails unless the FUZZY variable <var> (!X or ?X) is
currently bound.
(CONTEXT &<name>)
<name> is an atomic symbol which is to be the name of the
new active context (NIL is used to indicate the initial
context). The old (previously active) context name is
returned. All net modifications and accesses (including
STATE, FLUSH, and NETDIF) will only refer to the current
context, ignoring all other (inactive) contexts. Each
context initially starts out with an empty net. One can,
however, initialize a context (say CON2) to start out the
same as some other context (CON1) via the following:
(CONTEXT @CON1)
(SETQ S (CDR ZNET))
(CONTEXT @CON2)
(DO! (NETADD (LIST S NIL)))
Note that backtracking is independent of contexts. If a
backtrack point is established and changes are made to
several contexts, a subsequent RESTORE will undo all
changes made regardless of context. Note also that the
context feature concerns only the associative network of
assertions -- deduce, assert, and erase procedures are
independent of the context feature, and will be accessed
regardless of the current context.
(DEDUCE !<pat> !<zrange>)
Calls all deduce procedures which match <pat> until one
succeeds with a Z-value in the proper range. No search
of the associative net is made. The only pattern
functions allowed in <pat> after instantiation are ? and
?<name>. Each such pattern function must match either a
fully-instantiated item or another ?<name> in the
patterns of the deduce procedures called. See FETCH for
FUZZY REFERENCE MANUAL Page 18
a discussion of the optional <zrange> argument (note,
however, that in this case the order of the range bounds
is immaterial).
(DEMON: <proc> &<new demon>)
Same idea as ACCUM:.
(DO? &<e1> &<e2> . . .)
Evaluates each <ei> and returns the value of the last
one, except that it restores the system to its state
before the DO? was entered. Conceptually identical to:
((LAMBDA (S V) (RESTORE S) V) (SAVE) (DO . . .))
(DO! &<e1> &<e2> . . .)
Same idea as DO?, except everything is FINALIZEd so it
can't be undone upon subsequent backtracking.
Conceptually identical to:
((LAMBDA (S V) (FINALIZE S) V) (SAVE) (DO . . .))
(ERASE !<skel>)
Removes <skel> from the net and calls all erase
procedures which match <skel>. Fails if <skel> is not in
the net, or if any of the erase procedures fail (in which
case <skel> is restored). The erase procedures called
may initially access <skel> via (VAL) and the Z-value
associated with <skel> via (ZVAL).
(EXIT !<skel> &<zval>)
Exits from the current FOR statement with a value of
(<skel> . <zval>). Default <skel> is the instantiated
FOR pattern.
(*EXIT &<flag>)
This is the RUTGERS/UCI LISP function EXIT.
(FAIL &<state>)
Equivalent to (DO (RESTORE <state>) (SUCCEED FAIL)).
(FAILP &<exp>)
A LISP predicate which returns T if <exp> fails and NIL
otherwise (i.e., it simply does (EQ <exp> FAIL)).
Intended to be used to test for failure in a COND
statement.
FUZZY REFERENCE MANUAL Page 19
(FETCH !<pat> !<zrange>)
Fetches an assertion from the current net matching <pat>
whose Z-value is in the proper range. Fails if no such
assertion can be found. <zrange> may be either
[<upper>,<lower>] (return the assertion with the highest
Z-value in the range), [<lower>,<upper>] (return the
assertion with the lowest Z-value in the range), or
<lower> (same as [&ZHIGH,<lower>]). Default <zrange> is
&ZRANGE (initially [1,0]).
(FINALIZE &<state>)
Makes everything done since the SAVE which created
<state> non-RESTOREable. (FINALIZE) finalizes everything
done in the current PROC, or, if at the top level, fixes
things so nothing you've done can be undone. This should
be done occasionally, both to free up storage space and
to protect yourself against a backtrack error which would
undo everything you've done. Note that once a state has
been either RESTOREd or FINALIZEd, all states saved after
the original state are defunct. Subsequent attempts to
RESTORE to such a state will cause a backtrack error.
(FOR !<pat> !<list> &<e1> &<e2> . . .)
<list> should instantiate to a list. <pat> will be
matched successively against each item of <list> and, for
each successful match, the <ei>s will be evaluated. If
any of the <ei>s fail, or if a BACK is executed,
backtracking will occur and the next alternative will be
tried (there is an implied (BACK) at the end of the FOR).
The next alternative may be tried without backtracking
via NEXT, and the FOR may be exited via EXIT. Note that
the value of each <ei> is passed to the procedure demon
currently in effect just as if the expression occured at
the top level of the procedure.
(FOR DEDUCE: !<pat> ZVAL: !<zrange> &<e1> &<e2> . . .)
Iterates through all assertions obtainable via DEDUCE
which match <pat> and have a Z-value in the proper range.
Backtracking upon failure or BACK as described above.
The ZVAL: field is optional -- see FETCH for a
description of the <zrange> parameter (note, however,
that the deduced assertions will not necessarily be
ordered by Z-values). The value and Z-value portions of
each assertion are initially accessible via (VAL) and
(ZVAL) respectively. "DEDUCE:" may be replaced by "D:"
if desired.
FUZZY REFERENCE MANUAL Page 20
(FOR FETCH: !<pat> ZVAL: !<zrange> &<e1> &<e2> . . .)
Same as FOR DEDUCE:, except iterates through assertions
obtainable via FETCH. The assertions found will be
ordered in increasing or decreasing order by Z-value
(depending on the <zrange> argument). "FETCH:" may be
replaced by "F:" if desired.
(FOR GOAL: !<pat> ZVAL: !<zrange> &<e1> &<e2> . . .)
Same as FOR DEDUCE:, except iterates through assertions
obtainable via GOAL. Identical to FOR FETCH: followed
by FOR DEDUCE:. "GOAL:" may be replaced by "G:" if
desired.
(FOR TRY: !<list> !<pat> ZVAL: !<zrange> &<e1> &<e2> . . .)
<list> should instantiate to a list of procedure names.
Same as FOR DEDUCE:, except uses procedures in <list>
instead of deduce procedures. "TRY:" may be replaced by
"T:" if desired.
(GLOBAL <var1> <var2> . . .)
Informs the system that the indicated FUZZY variables are
global to all procedures, and they need not be listed in
the GLOBAL: field of each PROC. For example,
(GLOBAL !THIS)
.
.
.
(PROC GLOBAL: (!THAT) . . .)
allows the procedure to globally reference both !THIS and
!THAT. (GLOBAL) indicates that no variables are to be
considered global except those that are explicitly
indicated via GLOBAL: fields.
(GOAL !<pat> !<zrange>)
First performs a FETCH -- if unsuccessful performs a
DEDUCE.
(GOTO <tag>)
Transfers control to <tag> in the current procedure.
<tag> is evaluated if it is non-atomic.
(IF &<exp> THEN: &<s1> &<s2> . . . ELSE: &<f1> &<f2> . . .)
Evaluates <f1> <f2> . . . if <exp> returns FAIL or NIL,
otherwise evaluates <s1> <s2> . . .. Value is the value
of the last expression evaluated. If the THEN: is
missing and <exp> succeeds, the value of <exp> is
FUZZY REFERENCE MANUAL Page 21
returned. If the ELSE: is missing, "ELSE: FAIL" is
assumed.
(IFALL &<e1> &<e2> . . . THEN: &<s1> . . . ELSE: &<f1> . . .)
Similar to IF, except all of the <ei>s must succeed.
(IFANY &<e1> &<e2> . . . THEN: &<s1> . . . ELSE: &<f1> . . .)
Similar to IFALL, except only one of the <ei>s need
succeed.
(MATCH !<pat> !<skel>)
Matches <pat> against <skel>. Succeeds (with value
<skel>) only if the match succeeds.
(NETADD &<pair>)
<pair> is a list of two lists, the first containing
assertions (with Z-value modifiers) to be added to the
net, and the second assertions to be removed. In most
cases <pair> will be the value returned by a previous
NETDIF, and NETADD rebuilds a net which had been undone
by RESTORE. Subject to subsequent backtracking.
(NETDIF &<state>)
<state> is a backtrack point as created by SAVE (see
RESTORE for a discussion of default <state>s). The
"difference" between the current state of the net and its
previous state is computed -- the result is a list of two
lists, the first giving all assertions which appear in
the current net but not in the previous net, and the
second all assertions which appear in the previous net
but not in the current net. The net is not changed in
any way by NETDIF.
(NEXT !<skel> &<zval>)
Causes the current FOR statement to try the next
alternative (like BACK), except no backtracking is
performed. Default <skel> is the instantiated FOR
pattern.
(NOHASH <at1> <at2> . . .)
The indicated atomic symbols will not be hashed into the
associative net. Saves space and time for heavily-used
but not significant atoms.
FUZZY REFERENCE MANUAL Page 22
(POP <var>)
<var> should be a LISP (X) or FUZZY (!X) variable which
is bound to a list. The first member of the list will be
removed (and returned as the value of the POP). Subject
to subsequent backtracking.
(PROC NAME: <name> GLOBAL: <list> DEMON: <name> ZVAL: &<n>
ACCUM: &<n> <pat> <e1> <e2> . . .)
Defines a procedure and returns its name. The NAME:
through ACCUM: fields may appear in any order and are
all optional -- if missing, a unique name will be
generated by the system, a standard default demon
(*DEMON) will be used, and a Z-value of ZLOW and an
initial accumulated Z-value of ZHIGH will be assumed.
These default values may be changed if desired (see
discussion of DEFDEMON in section 3.4). <list> should be
a list of FUZZY variables which are global to this
procedure, e.g., (!X !Y !Z). Each <ei> is either an
expression to be evaluated or, if an atomic symbol, a tag
which may be transferred to (via GOTO). The value of
each <ei> will be passed to the demon (unless the demon
is NIL) for global control purposes. The value returned
by the demon is saved as the accumulated Z-value (subject
to subsequent backtracking), and may be referenced during
execution via the LISP variable ZACCUM.
(PUSH <var> &<exp>)
<var> should be a LISP (X) or FUZZY (!X) variable which
is bound to a list. The value of <exp> will be CONSed on
to the front of the list. Subject to subsequent
backtracking.
(PUSH? <var> &<exp>)
Identical to PUSH, except that no push is done if the
value of <exp> is already a MEMBER of the list to which
<var> is bound.
(RANGE &<low> &<high>)
Used to change the Z-value range. Sets ZLOW, ZHIGH,
ZRANGE, DEFZVAL, and DEFACCUM.
(REMOVE !<skel>) or (REMOVE <type> <proc>)
Removes <skel> from the current net, failing if <skel> is
not present. If the first argument is DEDUCE: (or D:),
ASSERT: (or A:), or ERASE: (or E:), a second argument
should be present giving a procedure name, e.g.,
(REMOVE DEDUCE: PROC1). Such procedures are still
defined, and may be accessed (by name) if desired.
Subject to subsequent backtracking.
FUZZY REFERENCE MANUAL Page 23
(*REMOVE &<x> &<l>)
This is the standard UCI LISP function REMOVE.
(RESTORE &<state>)
<state> should evaluate to a state as returned by SAVE.
All backtrackable modifications made since <state> was
created will be undone. Default <state> is the state
upon entry to the current procedure or, if not in a
procedure, the state at the time of the last top-level
FINALIZE.
(SAVE)
Establishes a backtrack point. The state which is
returned should be saved for later use as an argument to
RESTORE, FINALIZE, or NETDIF.
(SUCCEED !<skel> &<zval>)
Exits from the current procedure, returning a value of
(<skel> . <zval>). If <skel> and <zval> are absent, the
instantiated procedure pattern and accumulated Z-value
are returned.
(SUCCEED? !<skel> &<zval>)
Identical to SUCCEED, except the procedure may be
restarted (following the SUCCEED?) if invoked by a FOR
(DEDUCE:, GOAL:, or TRY:) statement. SUCCEED? may only
occur at the top level of a procedure or in a FOR
statement.
(SUCCEED! !<skel> &<zval>)
Equivalent to (DO (FINALIZE) (SUCCEED <skel> <zval>)).
(SUCCEEDP &<exp>)
Equivalent to (NOT (FAILP &<exp>)).
(TRY !<list> !<pat> !<zrange>)
<list> should instantiate to a list of procedure names.
Each will be called in turn with <pat> as its argument
until one succeeds with a Z-value in the proper range.
If none succeeds, the TRY fails. Note that TRY is
identical to DEDUCE, except that TRY allows the user to
specify particular procedures to try.
FUZZY REFERENCE MANUAL Page 24
(VAL &<exp>)
Returns the value portion of <exp>. If <exp> is missing,
the value of the last FETCH, DEDUCE, or GOAL statement is
used (the value portion of the latest instantiated
procedure pattern or FOR pattern may also be retrieved
via (VAL) until the first FETCH, DEDUCE, or GOAL
statement is evaluated).
(ZADDPROP &<at> &<val> &<prop>)
Identical to the RUTGERS/UCI LISP function ADDPROP (adds
<val> to the list stored under the <prop> property of
<at>), except subject to subsequent backtracking. The
list being built should be retrieved via ZGET instead of
GET.
(ZAND THRESH: &<thresh> &<e1> &<e2> . . .)
Evaluates each of the <ei>s, returning the value of the
last <ei> evaluated and a Z-value equal to the minimum of
←←←←←←←
all the <ei>s. Fails if the Z-value falls below <thresh>
or any of the <ei>s fail. Default <thresh> is ZLOW.
(ZGET &<at> &<prop>)
Should be used to GET values off of property lists which
were stored via ZPUT or ZADDPROP.
(ZNOT &<exp>)
Returns the value of <exp> with a Z-value of ZLOW plus
ZHIGH minus (ZVAL <exp>).
(ZPUT &<at> &<val> &<prop>)
Backtrackable version of PUTPROP. Use ZGET to retrieve
instead of GET.
(ZOR THRESH: &<thresh> &<e1> &<e2> . . .)
Similar to ZAND except returns the maximum of the
←←←←←←←
Z-values of the individual expressions.
(ZREMPROP &<at> &<prop>)
Backtrackable version of REMPROP. Should only be used to
remove values placed on property lists using ZPUT or
ZADDPROP.
(ZVAL &<exp>)
Similar to VAL, except returns the Z-value portion of
<exp>. If no Z-value is present, ZHIGH is returned
(unless <exp> is FAIL, in which case ZLOW is returned).
FUZZY REFERENCE MANUAL Page 25
(ZVAL: <proc> &<new zval>)
Same idea as ACCUM: and DEMON:.
3.3 Pattern Functions
←←←←←←←←←←←←←←←←←←←←←
@<stuff> or (QUOTE <stuff>)
Stops instantiation just as it stops evaluation in LISP.
Thus if !X is bound to A, (@!X !X) instantiates to
(!X A).
!<name> or (*! <name>)
Returns the FUZZY value of !<name>. If !<name> is
unbound, acts like ?<name>. May also be used with a
skeletal argument to cause instantiation where evaluation
would normally occur, e.g., (PRINT !(VAL: !X)).
!!<name> or (*!! <name>)
If !<name> is bound to a list, it is spliced into the
skeleton at this point. If !<name> is bound to an atom,
"!!" has no effect. If !<name> is unbound, acts like
??<name>.
&<exp> or (*& <exp>)
Returns the LISP value of <exp>. May be used to cause
evaluation where instantiation would normally occur.
&&<exp> or (*&& <exp>)
If <exp> evaluates to a list, it is spliced into the
skeleton at this point. If <exp> evaluates to an atom,
"&&" has no effect.
? or (*?)
Matches any single item.
?<name> or (*? <name>)
Matches any single item, binding the item to the FUZZY
variable !<name>. All of the "?" and "??" assignment
operators are subject to subsequent backtracking.
?@<name> or (*?Q <name>)
Same as ?<name>, except will match anything, including an
←←←←←←←←
uninstantiated pattern (i.e., a pattern which was
quoted). All other pattern functions will attempt to
match only a fully-instantiated skeleton (except that
?<name> in a procedure pattern may be matched with
FUZZY REFERENCE MANUAL Page 26
another ?<name> in the calling pattern).
?? or (*??)
Matches a segment of zero or more items. Subsequent
failures by the matcher (within the current segment)
cause another item to be matched.
??<name> or (*?? <name>)
Matches a segment of zero or more items, binding the
segment matched to the FUZZY variable !<name> (!<name> is
initially given a value of NIL).
??:<name> or (*??: <name>)
Matches a segment of zero or more items, binding the
length of the segment matched to the FUZZY variable
←←←←←←
!<name>.
(*AND !<pat1> !<pat2> . . .)
Succeeds only if each of the <pat>s match. For example,
(*AND ?PAIR (?X ?Y)) will match an ordered pair,
assigning the pair to !PAIR and the first and second
items to !X and !Y.
(*ANY !<pat> !<list>)
<list> should instantiate to a list. *ANY will attempt
to match <pat> only if the matchee is EQUAL to a member
of <list>.
(*CON !<pat> !<object>)
<object> should instantiate to an arbitrary LISP object.
*CON will attempt to match <pat> only if the matchee
contains <object> at some level.
(*LEN !<pat> &<n>)
Matches <pat> against a segment of length <n>, e.g.,
(MATCH [A (*LEN ?X 2) ??] [A B C D E])
binds !X to (B C). If <n> evaluates to 0, nothing is
matched against <pat> and the match continues (i.e., the
*LEN is ignored).
(*NOT !<pat> !<test-pat>)
Attempts to match <pat> only if <test-pat> does not
match. For example, (*NOT ?X (*OR A B)) will match
anything except A or B, binding it to !X.
FUZZY REFERENCE MANUAL Page 27
(*OPT !<pat>)
Indicates that <pat> is optional. If it doesn't match it
is ignored.
(*OR !<pat1> !<pat2> . . .)
Succeeds if one of the <pat>s matches.
(*R !<pat> &<exp>)
May be used to place restrictions on the match. First
attempts to match <pat>. If it matches, <exp> is
evaluated -- if it evaluates to NIL or FAIL, the match
fails; else it succeeds. For example,
(*R ?N (NUMBERP !N))
will only match a number, and
(*R ?OB (FETCH (RED !OB)))
will only match a red object. (*R ?<var>) may be used in
deduce procedure patterns to insure that ?<var> is
matched only against a fully-instantiated skeleton (i.e.,
not another ?<var1> variable).
(*REP !<pat> &<n>)
Matches <pat> against each of the next <n> items. Fails
if <pat> fails to match an item. For example, (*REP ? 5)
will skip the next five items. If <n> is missing, *REP
continues until <pat> fails to match, e.g., (*REP X) will
span a string of X's.
3.4 Variables of Interest
←←←←←←←←←←←←←←←←←←←←←←←←←
The following LISP variables might be of interest to the
FUZZY user. Note that all variable names beginning with "Z" are
the property of the FUZZY system.
FAIL, DONE
These variables are bound to themselves (like NIL).
ZHIGH, ZLOW, ZRANGE
ZHIGH specifies the highest possible Z-value, and has an
initial value of 1. ZLOW specifies the lowest possible
Z-value, and is initially 0. ZRANGE gives the default
Z-value range for FETCH, DEDUCE, etc., and is initially
[1,0]. May all be set via the RANGE function.
FUZZY REFERENCE MANUAL Page 28
DEFDEMON, DEFZVAL, DEFACCUM
DEFDEMON is bound to the name of the default demon to be
used when a procedure is defined and the DEMON: field is
missing. It is initially *DEMON, but may be changed if
desired (e.g., changing it to NIL changes the default to
no demon calls). Default procedure Z-values and initial
accumulated Z-values other than ZLOW and ZHIGH may be
associated with particular demons by placing the desired
value on the property list of the demon name under the
indicator DEFZVAL or DEFACCUM. For example, if the demon
AVDEMON wanted its accumulated Z-value to initially be
(0 . 0), one would simply do:
(PUT @AVDEMON @(0 . 0) @DEFACCUM)
If the ZVAL: or ACCUM: field is missing and no default
value is present on the property list of the demon name,
the value of DEFZVAL or DEFACCUM is used. These values
are initially ZLOW and ZHIGH, respectively, and may be
changed via the RANGE function.
ZACCUM, ZNAME
The procedure being executed may reference the current
accumulated Z-value via the variable ZACCUM. A demon may
reference the name of the procedure being executed via
ZNAME.
ZALIST
The current FUZZY variable bindings are stored in a list
which is bound to ZALIST. This list is rebound each time
a procedure is entered, and is used when any local
variables are subsequently defined. If it is desired to
set up a local environment for FUZZY variables in a LISP
function, simply include ZALIST as a PROG variable. All
FUZZY variables referenced will then refer to this local
environment.
ZNET, DPROCS, APROCS, EPROCS
(CDR ZNET) is a list of all assertions in the current
associative net (i.e., the current context). The CDR of
DPROCS, APROCS, or EPROCS is a list of procedure names
which have been declared as deduce, assert, or erase
procedures. Note that these lists may be examined, but
they should not be modified as there are various other
←←←
structures which maintain pointers into them.
ZGLOBEV
This is the list of variables which are considered global
to all procedures. It is reset with each GLOBAL
statement, or may be modified directly if desired.
FUZZY REFERENCE MANUAL Page 29
3.5 Debugging Aids
←←←←←←←←←←←←←←←←←←
FUZZY is fully integrated with conventional UCI LISP
debugging aids. The prettyprinter (PP, PPL) and the editor
(EDITF) are both aware of FUZZY procedures and handle them
correctly. Several functions (PROC, FOR, IF) are flagged as
printmacros in order to prettyprint prettier. The various prefix
characters (!, ?, &) are defined as readmacros which expand into
the proper internal format, and as printmacros so that they
prettyprint correctly. Note that any constructs in the break
package or editor which start with !, ?, or & (e.g., ?=, !0,
etc.) must be preceded by a slash (/) in order to be utilized (or
see FUZZYMACS below).
When a FUZZY error is encountered a message is printed and a
normal error break is made to the break package. Usually the
error is fatal, but you may attempt to continue by RETURNing an
appropriate value.
It should be noted that when FUZZY is started the user's
normal (INIT.LSP) file and, if present, an (INIT.FUZ) file are
loaded.
The following functions are available for printing, dumping,
flushing, and tracing the associative net and FUZZY procedures.
(STATE <flag>)
When printing to the terminal, (STATE) prints out the
current state of the associative net and all deduce,
assert, and erase procedures. (STATE NET) only prints
the net, and (STATE PROCS) only prints the procedures.
When printing to a file (e.g., via DSKOUT), the net
and/or procedures are dumped in such a way that they will
be restored upon input. The normal way to save the state
of the system is thus:
(DSKOUT <file> (STATE) (PP <other procs & funcs>))
Of course, if you only want to save the procedures and
not the assertions in the net, (STATE) may be replaced by
(STATE PROCS).
(FLUSH <flag>)
(FLUSH) removes all assertions and procedures from
FUZZY's associative net. (FLUSH NET) only removes the
assertions, and (FLUSH PROCS) only removes the
procedures. Note that all procedures removed remain
defined, and may still be accessed (by name) if desired.
FUZZY REFERENCE MANUAL Page 30
(ZTRACE <a1> <a2> . . .)
Causes each <ai> to be traced, where <ai> can be either
an <atom> [equivalent to (<atom> T NIL)], (<atom> <e>)
[equivalent to (<atom> <e> NIL)], or (<atom> <e1> <e2>).
The first expression (<e1>) is interpreted as a
conditional trace condition (i.e., the atom is traced
only if it evaluates to non-NIL), and the second
expression (<e2>) is interpreted as a conditional break
condition (i.e., the atom is also broken if it evaluates
to non-NIL). If <e2> is the special atomic symbol DITTO
the break condition is the same as the trace condition.
The <atom> can be either the name of a proc or one of the
following special atoms:
PROCS all procs
ADD all additions to the net
REMOVE all removals from the net
FETCH all retrievals from the net
NET all net accesses (= ADD, REMOVE, and FETCH)
The trace and break conditions can access the assertion
being added, removed, or fetched from the net (consed to
its Z-value) or the skeleton being passed to a proc via
the LISP variable *ARG.
(ZUNTRACE <at1> <at2> . . .)
Untraces the specified atoms. (ZUNTRACE) turns off all
FUZZY tracing and breaking.
(FUZZYMACS &<flag>)
May be used to turn the FUZZY macro characters (?, !, and
&) off (<flag>=NIL) and back on (<flag>=T).
FUZZY REFERENCE MANUAL Page 31
4. REFERENCES
←←←←←←←←←←←←←
[1] LeFaivre, R.: "FUZZY: A Programming Language for Fuzzy
Problem-Solving", Technical Report No. 202, Computer
Sciences Dept., University of Wisconsin (1974).
[2] LeFaivre, R.: "Fuzzy Problem-Solving", Ph.D. Dissertation,
Computer Sciences Dept., University of Wisconsin.
Available as Technical Report No. 37, Madison Academic
Computing Center, University of Wisconsin (1974).
[3] LeFaivre, R.: "The Representation of Fuzzy Knowledge", J. of
←← ←←
Cybernetics, 4, 57-66 (1974).
←←←←←←←←←←← ←
[4] LeFaivre, R.: "Procedural Representation in a Fuzzy
Problem-Solving System", Proc. National Computer Conf.,
←←←←← ←←←←←←←← ←←←←←←←← ←←←←←
New York (1976).
[5] LeFaivre, R.: "Fuzzy Representation and Approximate
Reasoning", RUCBM-TR-78, Computer Science Dept., Rutgers
University (1977).
[6] Bobrow, D. and B. Raphael: "New Programming Languages for
Artificial Intelligence Research", Computing Surveys, 6,
←←←←←←←←← ←←←←←←← ←
153-174 (1974).
[7] Kling, R.: "FUZZY-PLANNER: Reasoning with Inexact Concepts
in a Procedural Problem-Solving Language", J. of
←← ←←
Cybernetics, 4, 105-122 (1974).
←←←←←←←←←←← ←
FUZZY REFERENCE MANUAL Page 32
INDEX
←←←←←
! . . . . . . . . . . . . . . . . . . . . 5-6, 25, 29-30
!! . . . . . . . . . . . . . . . . . . . . 5-6, 25
& . . . . . . . . . . . . . . . . . . . . 5-6, 25, 29-30
&& . . . . . . . . . . . . . . . . . . . . 5-6, 25
*! . . . . . . . . . . . . . . . . . . . . 25
*!! . . . . . . . . . . . . . . . . . . . 25
*& . . . . . . . . . . . . . . . . . . . . 25
*&& . . . . . . . . . . . . . . . . . . . 25
*? . . . . . . . . . . . . . . . . . . . . 25
*?? . . . . . . . . . . . . . . . . . . . 26
*??: . . . . . . . . . . . . . . . . . . . 26
*?Q . . . . . . . . . . . . . . . . . . . 25
*AND . . . . . . . . . . . . . . . . . . . 7, 26
*ANY . . . . . . . . . . . . . . . . . . . 7, 26
*ARG . . . . . . . . . . . . . . . . . . . 30
*CON . . . . . . . . . . . . . . . . . . . 7, 26
*DEMON . . . . . . . . . . . . . . . . . . 11, 22
*EXIT . . . . . . . . . . . . . . . . . . 18
*LEN . . . . . . . . . . . . . . . . . . . 26
*NOT . . . . . . . . . . . . . . . . . . . 26
*OPT . . . . . . . . . . . . . . . . . . . 27
*OR . . . . . . . . . . . . . . . . . . . 7, 27
*R . . . . . . . . . . . . . . . . . . . . 7, 27
*REMOVE . . . . . . . . . . . . . . . . . 23
*REP . . . . . . . . . . . . . . . . . . . 27
? . . . . . . . . . . . . . . . . . . . . 6, 25, 29-30
?? . . . . . . . . . . . . . . . . . . . . 6, 26
??: . . . . . . . . . . . . . . . . . . . 26
?@ . . . . . . . . . . . . . . . . . . . . 25
@ . . . . . . . . . . . . . . . . . . . . 25
ACCUM: . . . . . . . . . . . . . . . . . . 12, 16, 22
ADD . . . . . . . . . . . . . . . . . . . 4, 14, 16
APROCS . . . . . . . . . . . . . . . . . . 28
ASSERT . . . . . . . . . . . . . . . . . . 14, 16
Assert Procedure . . . . . . . . . . . . . 14
Assertion . . . . . . . . . . . . . . . . 4
BACK . . . . . . . . . . . . . . . . . . . 9, 16, 19
BIND . . . . . . . . . . . . . . . . . . . 6, 17
BIND! . . . . . . . . . . . . . . . . . . 8, 17
BOUND . . . . . . . . . . . . . . . . . . 17
CONTEXT . . . . . . . . . . . . . . . . . 7, 17
DEDUCE . . . . . . . . . . . . . . . . . . 14, 17, 19
Deduce Procedure . . . . . . . . . . . . . 14, 17
DEFACCUM . . . . . . . . . . . . . . . . . 22, 28
DEFDEMON . . . . . . . . . . . . . . . . . 22, 28
DEFZVAL . . . . . . . . . . . . . . . . . 22, 28
DEMON: . . . . . . . . . . . . . . . . . . 12, 18, 22
DO! . . . . . . . . . . . . . . . . . . . 8, 18
DO? . . . . . . . . . . . . . . . . . . . 8, 18
DONE . . . . . . . . . . . . . . . . . . . 11, 27
DPROCS . . . . . . . . . . . . . . . . . . 28
EDITF . . . . . . . . . . . . . . . . . . 29
EPROCS . . . . . . . . . . . . . . . . . . 28
ERASE . . . . . . . . . . . . . . . . . . 14, 18
Erase Procedure . . . . . . . . . . . . . 14, 18
EXIT . . . . . . . . . . . . . . . . . . . 9, 18-19
FAIL . . . . . . . . . . . . . . . . . . . 3, 10, 18, 24, 27
FAILP . . . . . . . . . . . . . . . . . . 18
FETCH . . . . . . . . . . . . . . . . . . 4, 19-20
FINALIZE . . . . . . . . . . . . . . . . . 8, 10, 19, 23
FLUSH . . . . . . . . . . . . . . . . . . 29
FOR . . . . . . . . . . . . . . . . . . . 8-9, 11, 19, 29
FOR DEDUCE: . . . . . . . . . . . . . . . 14, 19
FOR FETCH: . . . . . . . . . . . . . . . . 9, 20
FOR GOAL: . . . . . . . . . . . . . . . . 14, 20
FOR TRY: . . . . . . . . . . . . . . . . . 13, 20
FUZZYMACS . . . . . . . . . . . . . . . . 29-30
GLOBAL . . . . . . . . . . . . . . . . . . 10, 20
GLOBAL: . . . . . . . . . . . . . . . . . 10, 20, 22
GOAL . . . . . . . . . . . . . . . . . . . 14, 20
GOTO . . . . . . . . . . . . . . . . . . . 10, 20
IF . . . . . . . . . . . . . . . . . . . . 20, 29
IFALL . . . . . . . . . . . . . . . . . . 21
IFANY . . . . . . . . . . . . . . . . . . 21
Instantiation . . . . . . . . . . . . . . 4-5
MATCH . . . . . . . . . . . . . . . . . . 6, 21
NAME: . . . . . . . . . . . . . . . . . . 10, 22
NETADD . . . . . . . . . . . . . . . . . . 21
NETDIF . . . . . . . . . . . . . . . . . . 8, 21
NEXT . . . . . . . . . . . . . . . . . . . 9, 19, 21
NOHASH . . . . . . . . . . . . . . . . . . 21
Pattern . . . . . . . . . . . . . . . . . 4, 6, 13
POP . . . . . . . . . . . . . . . . . . . 22
PP . . . . . . . . . . . . . . . . . . . . 29
PPL . . . . . . . . . . . . . . . . . . . 29
PROC . . . . . . . . . . . . . . . . . . . 10, 22, 29
Procedure Demon . . . . . . . . . . . . . 11-12
PUSH . . . . . . . . . . . . . . . . . . . 22
PUSH? . . . . . . . . . . . . . . . . . . 22
QUOTE . . . . . . . . . . . . . . . . . . 25
RANGE . . . . . . . . . . . . . . . . . . 3, 22, 27-28
REMOVE . . . . . . . . . . . . . . . . . . 5, 22
RESTORE . . . . . . . . . . . . . . . . . 8-10, 19, 23
SAVE . . . . . . . . . . . . . . . . . . . 7, 9, 23
Skeleton . . . . . . . . . . . . . . . . . 4, 6
STATE . . . . . . . . . . . . . . . . . . 29
SUCCEED . . . . . . . . . . . . . . . . . 10, 23
SUCCEED! . . . . . . . . . . . . . . . . . 10, 23
SUCCEED? . . . . . . . . . . . . . . . . . 15, 23
SUCCEEDP . . . . . . . . . . . . . . . . . 23
TRY . . . . . . . . . . . . . . . . . . . 13, 20, 23
VAL . . . . . . . . . . . . . . . . . . . 3, 16, 18-19, 24
Variable . . . . . . . . . . . . . . . . . 6, 28
ZACCUM . . . . . . . . . . . . . . . . . . 22, 28
ZADDPROP . . . . . . . . . . . . . . . . . 24
ZALIST . . . . . . . . . . . . . . . . . . 28
ZAND . . . . . . . . . . . . . . . . . . . 3, 24
ZGET . . . . . . . . . . . . . . . . . . . 24
ZGLOBEV . . . . . . . . . . . . . . . . . 28
ZHIGH . . . . . . . . . . . . . . . . . . 3, 22, 27
ZLOW . . . . . . . . . . . . . . . . . . . 3, 22, 27
ZNAME . . . . . . . . . . . . . . . . . . 28
ZNET . . . . . . . . . . . . . . . . . . . 28
ZNOT . . . . . . . . . . . . . . . . . . . 3, 24
ZOR . . . . . . . . . . . . . . . . . . . 3, 24
ZPUT . . . . . . . . . . . . . . . . . . . 24
ZRANGE . . . . . . . . . . . . . . . . . . 5, 19, 22, 27
ZREMPROP . . . . . . . . . . . . . . . . . 24
ZTRACE . . . . . . . . . . . . . . . . . . 30
ZUNTRACE . . . . . . . . . . . . . . . . . 30
ZVAL . . . . . . . . . . . . . . . . . . . 3, 16, 18-19, 24
ZVAL: . . . . . . . . . . . . . . . . . . 12, 22, 25